# 第一题
d = [3, 9, 12, 35, 5, 7, 10]

# 堆排序


def heap_adjust(data, n, i):

    while 2 * i <= n:
        max_tree_index = 2 * i
        right_tree_index = 2 * i + 1
        if right_tree_index <= n:
            if data[max_tree_index] < data[right_tree_index]:
                max_tree_index = right_tree_index
        if data[max_tree_index] > data[i]:
            data[i], data[max_tree_index] = data[max_tree_index], data[i]
            i = max_tree_index
        else:
            break


def heap(data, n):
    a = n//2
    for i in range(a, 0, -1):
        heap_adjust(data, n, i)


def heap_sort(data, reverse=False):
    data1 = [0] + data
    length = len(data1)
    n = length - 1
    heap(data1, n)
    for i in range(n, 1, -1):
        data1[1], data1[i] = data1[i], data1[1]
        heap_adjust(data1, i-1, 1)
    return data1[1:] if not reverse else data1[-1:-length:-1]


print(heap_sort(d, reverse=True))
print(heap_sort(d))

# 选择排序


def selction_sort(data, reverse=False):

    length = len(data)
    n = length // 2

    for i in range(n):
        maxindex = i
        minindex = i
        for j in range(i+1, length-i):
            if data[j] > data[maxindex]:
                maxindex = j
            if data[j] < data[minindex]:
                minindex = j

        if data[maxindex] == data[minindex]:break

        if maxindex != length-i-1:
            data[length-i-1], data[maxindex] = data[maxindex], data[length-i-1]
            if minindex == length-i-1:
                minindex = maxindex

        if i != minindex and data[i] != data[minindex]:
            data[i], data[minindex] = data[minindex], data[i]

    return data if not reverse else data[-1:-length-1:-1]


print(selction_sort(d, reverse=True))
print(selction_sort(d))

# 冒泡法


def bubble_sort(data, reverse=False):
    length = len(data)

    for i in range(length-1):
        flag = False
        for j in range(length-i-1):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                flag = True
        if not flag:
            break

    return data if not reverse else data[-1:-length-1:-1]


print(bubble_sort(d, reverse=True))
print(bubble_sort(d))

# 第二题
lst1 = [1, 2, 3]
lst2 = ['a', 'b', 'c']


def exchange(lst1, lst2):
    lst1[0], lst2[0] = lst2[0], lst1[0]
    lst1[-1], lst2[-1] = lst2[-1], lst1[-1]


exchange(lst1, lst2)
print(lst1)
print(lst2)

# 算法掌握的非常不错，思路和结果都是对的，最后一道题可以尝试着把两行写成一行。